'''
Godleib development 21.06.2020
'''
author = 'Godleib'

import numpy

'''
Extended Euclidean algorithm

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
'''
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, x, y = egcd(b % a, a)
        return (g, y - (b // a) * x, x)

 # x = mulinv(b) mod n, (x * b) % n == 1

# ������ ���� ������ https://www.cyberforum.ru/python-beginners/thread1770117.html

# ����������������� �������� � b �� ������ n
def mulinv(b, n):
    g, x, _ = egcd(b, n)
   # print(g,x,_)
    if g == 1:
        return x % n

# ���
def hcfnaive(a,b):
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)


#������� �����?
def IsPrime(n):
    d = 2
    while d * d <= n and n % d != 0:
        d += 1
    return d * d > n

# Main
s = [2,7,11,21,42,89,180,354] #�������� �������
print(s)
length = len(s)
print ('������',length)

Sum_s=0 #����� ���������
for element in s:
    Sum_s = Sum_s + element
print("����� ���������(Sum_s):",Sum_s)

#���� �� ���� q, ���� ���� - ������ while ��� ����
q = 881#Sum_s
#while not IsPrime(q):
#    q = q + 1
print("������� ����� q ������������� Sum_s:",q)

#���� �� ���� r, ���� ���� - ������ while ��� ����
r = 588#Sum_s
#while not IsPrime(r):
#    r = r-1
print("r ������ ���� ������� ������ � q: ",end='')

gcd = hcfnaive(q,r)
print("���(r,q)=",gcd,'; r =',r)

print('�������� ����(',Sum_s,q,r,')')
print('�������� ���� ������ �� ����-�� betta, betta_i = r*s_i mod q')


betta = []
for count in range(0,length):
    a = s[count]*r % q
    betta.append(a)
    print (s[count],'*',r,'mod',q,'=',a)
print('�������� ����: ('+', '.join( map(str,betta))+')')

def bit (num,bitnum):
    return int (str(num)[- (bitnum+1)])


print ('������� ��� ���� �����������(������� � �������� ������� ���������)')
Alice = str(input())

Alice_sum = 0

print('�������� ������ ��� �� betta_i')

for count in (range (0,len(Alice))):
    if (count < len(Alice) - 1):
        Alice_sum = Alice_sum + int(betta[-(count+1)]) * bit (Alice,count)
        print (betta[-(count+1)],'*',bit(Alice,count),'+ ', end='')
    else:
        Alice_sum = Alice_sum + int(betta[-(count+1)]) * bit (Alice,count)
        print (betta[-(count+1)],'*',bit(Alice,count),'= ', end='')

print (Alice_sum)


mi = mulinv(r, q)
print('������ ����������������� �������� r �� ������ q (� ������� ������������ ��������� �������), ��� ����� =',mi)

a = Alice_sum * mi % q
print (Alice_sum,'*',mi,'mod',q,'=',a)


difference = 1
b = a
ans = []
while  difference > 0:
    for count in range(0,length):
        if s[count] > b:
            i = count - 1
            #print(0)
            break
        else :
            i = length - 1
            #print(1)
    ans.append(i)

    w = s[i]
    difference = b - w
    print(b,'-',w,'=',difference)
    b = difference

arr_ans =[]
arr_ans = [0] * length
for count in ans :
    arr_ans[count] = 1
#print (arr_ans)
print ('��������, ������� ���� ������� �� ������� (',', '.join((map(str,reversed(ans)))),') ����� ��������������� 1 � �������� ������, � ������ :',', '.join(map(str,(arr_ans))),'!')


print()
print()
print()
print()

print('@'+author+'development')